package com.krahets88.doublepointer;

import org.junit.jupiter.api.Test;

import java.util.HashSet;

public class Question142 {
    @Test
    public void test1() {
//        ListNode node1 = new ListNode(3);
//        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(0);
//        ListNode node4 = new ListNode(4);
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node2;
//        Solution solution = new Solution();
//        solution.detectCycle(node1);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        node1.next = node2;
        node2.next = node1;
        SolutionTwo solution = new SolutionTwo();
        solution.detectCycle(node1);
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public class Solution {

        public ListNode detectCycle(ListNode head) {
            HashSet<ListNode> nodes = new HashSet<>();
            while (head != null) {
                if (!nodes.contains(head)) {
                    nodes.add(head);
                } else {
                    return head;
                }
                head = head.next;
            }
            return null;
        }
    }

    public class SolutionTwo {
        public ListNode detectCycle(ListNode head) {
            ListNode fast = head, slow = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if(fast==slow){ //第一次相遇后，重新制造第二次相遇
                    slow=head;
                    while(slow!=fast){
                        slow=slow.next;
                        fast=fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }

    }
}
